/************************************************************************************************
 * test examples of 100 interesting program in C
 * test 034.c
 * 1~16 the magic square with prime couples
 ***********************************************************************************************/

#include <stdio.h>
#include <string.h>

/*
 * divide odd and even intto 2 used array may accelerate somehow
 */

#define WIDTH 4
#define MAX (WIDTH*WIDTH)

int p[MAX][MAX];

int isPrime(int n)
{
	if (n < 2) return(0);
	else if (n == 2) return(1);
	else if (n%2 == 0) return(0);
	int i = 0;
	for (i = 3; i <= n/2; i += 2)
		if (n%i == 0) return(0);
	return(1);
}

int setPrimeArray()
{
	memset(p, 0, sizeof(int)*MAX*MAX);
	int i = 0, j = 0;
	for (i = 1; i <= MAX; i++)
	{
		int curr = 0;
		for (j = 1; j <= MAX; j++)
		{
			if (i == j) continue;
			if (isPrime(i+j))
				p[i-1][curr++] = j;
		}
	}
}

int printPrimeArray()
{
	int i = 0, j = 0;
	for (i = 1; i <= MAX; i++)
	{
		printf("%2d: ", i);
		for (j = 1; j <= MAX && p[i-1][j-1] != 0; j++)
			printf("%3d", p[i-1][j-1]);
		printf("\n");
	}
}

int square[MAX];
int used[MAX];

int printSquare()
{
	int i = 0, j = 0;
	printf("\n");
	for (i = 0; i < WIDTH; i++)
	{
		for (j = 0; j < WIDTH; j++)
			printf("%3d", square[i*WIDTH+j]);
		printf("\n");
	}
}

int fillSquare(int n, int pos)
{
	// do
	square[pos-1] = n;
	used[n-1] = 1;
	
	int flag = 0;

	// last element
	if (pos == MAX)
	{
		// printSquare();
		flag = 1;
	}
	else
	{
		// next element is on the first row
		if ((pos+1) <= WIDTH)
		{
			int i = 0;
			for (i = 0; p[n-1][i] != 0; i++)
				if (used[p[n-1][i]-1] != 1)
					flag += fillSquare(p[n-1][i], pos+1);
		}
		// next element is on the first line
		else if ((pos+1)%4 == 1)
		{
			int i = 0, t = square[pos-4];
			for (i = 0; p[t-1][i] != 0; i++)
				if (used[p[t-1][i]-1] != 1)
					flag += fillSquare(p[t-1][i], pos+1);
		}
		// next element should be decided by two element
		else
		{
			int i = 0, j = 0, t = square[pos-4];
			for (i = 0, j = 0; p[n-1][i] != 0; i++)
			{
				if (used[p[n-1][i]-1] == 1) continue;
				else
				{
					for (; p[t-1][j] != 0; j++)
					{
						if (p[t-1][j] < p[n-1][i]) continue;
						else if (p[t-1][j] > p[n-1][i]) break;
						else
							// this situation won't happen
							// bcz it was evaluated as p[n-1][i]-1 (they are equal) in out loop
							// if (used[p[t-1][j]-1] == 1) break;
							// else
							flag += fillSquare(p[t-1][j], pos+1);
							// need not break
							// j++ will lead to break
					}
				}
			}					
		}
	}

	// undo, don't forget undo before any "return"
	used[n-1] = 0;
	square[pos-1] = 0;

	return(flag);
}
int main()
{
	setPrimeArray();
	printPrimeArray();

	memset(square, 0, sizeof(int)*MAX);
	memset(used, 0, sizeof(int)*MAX);

	int i = 0, count = 0;
	for (i = 1; i <= MAX; i++)
		count = fillSquare(i, 1);
	printf("Total %d squares with prime couples\n", count);
}
